//给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
// -1。 
//
// 
//
// 示例 1: 
//
// 输入: coins = [1, 2, 5], amount = 11
//输出: 3 
//解释: 11 = 5 + 5 + 1 
//
// 示例 2: 
//
// 输入: coins = [2], amount = 3
//输出: -1 
//
// 
//
// 说明: 
//你可以认为每种硬币的数量是无限的。 
// Related Topics 动态规划 
// 👍 790 👎 0


package com.yun.leetcode.editor.cn;

import java.util.Arrays;

public class CoinChange {
    public static void main(String[] args) {
        Solution solution = new CoinChange().new Solution();
        int[] coins = new int[]{1, 2, 5};
        System.out.println(solution.coinChange(coins, 11));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 现在版本
        // 背包问题，后面的需要借助前面的。
        //
        public int coinChange(int[] coins, int amount) {
            int[] ary = new int[amount + 1];
            Arrays.fill(ary, amount + 1);
            ary[0] = 0;
            for (int i = 1; i < amount + 1; i++) { // 注意此时边界值，需要多循环一次，需要从1开始循环
                for (int coin : coins) {
                    if (coin <= i) {
                        // 硬币面值小于等于金额
                        ary[i] = Math.min(ary[i], ary[i - coin] + 1);
                    }
                }
            }
            return ary[amount] == amount + 1 ? -1 : ary[amount];
        }
        // 以前版本
//        public int coinChange(int[] coins, int amount) {
//            if (coins == null || coins.length == 0 || amount == 0) {
//                return 0;
//            }
//            int len = coins.length;
//            int[][] dp = new int[len][amount + 1];
//            // 首列
//            for (int j = 1; j <= amount; j++) { // j<=钱的总额，记一下
//                dp[0][j] = Integer.MAX_VALUE;
//                if (j - coins[0] >= 0 && dp[0][j - coins[0]] != Integer.MAX_VALUE) {
//                    dp[0][j] = dp[0][j - coins[0]] + 1;
//                }
//            }
//            int left = 0;
//            for (int i = 1; i < len; i++) {
//                for (int j = 1; j <=amount; j++) {
//                    left = Integer.MAX_VALUE;
//                    if (j - coins[i] >= 0 && dp[i][j - coins[i]] != Integer.MAX_VALUE) {
//                        left = dp[i][j - coins[i]] + 1;
//                    }
//                    dp[i][j] = Math.min(left, dp[i - 1][j]);
//
//                }
//            }
//
//            return dp[len - 1][amount] == Integer.MAX_VALUE ? -1 : dp[len - 1][amount];
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}